#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

namespace S1 {
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int middle = left + ((right - left) >> 1);  // 防止溢出
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }

    return -1;
}
};  // namespace S1

namespace S2 {
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();

    while (left < right) {
        int middle = left + ((right - left) >> 1);  // 防止溢出
        if (nums[middle] > target) {
            right = middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }

    return -1;
}
};  // namespace S2

int main() {
    vector<int> nums1{-1, 0, 3, 5, 9, 12}, nums2{-1, 0, 3, 5, 9, 12};
    int target1 = 9, target2 = 2;
    int output1 = 4, output2 = -1;

    assert(S1::search(nums1, target1) == output1);
    assert(S1::search(nums2, target2) == output2);

    assert(S2::search(nums1, target1) == output1);
    assert(S2::search(nums2, target2) == output2);

    return 0;
}